package com.zrf.base.knowledge.leetcode.editor.cn;

/**
 * //给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * //
 * // 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * //
 * // 注意:
 * //不能使用代码库中的排序函数来解决这道题。
 * //
 * // 示例:
 * //
 * // 输入: [2,0,2,1,1,0]
 * //输出: [0,0,1,1,2,2]
 * //
 * // 进阶：
 * //
 * //
 * // 一个直观的解决方案是使用计数排序的两趟扫描算法。
 * // 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
 * // 你能想出一个仅使用常数空间的一趟扫描算法吗？
 * //
 * // Related Topics 排序 数组 双指针
 * // 👍 701 👎 0
 *
 * @author zhouruifeng
 * @date 2020-11-16 07:10:34
 */
public class SortColors {
    public static void main(String[] args) {
        Solution solution = new SortColors().new Solution();
        int[] nums = new int[]{2,0,2,1,1,0};
        solution.sortColors(nums);
        System.out.println(nums);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void sortColors(int[] nums) {
//            singleReferer(nums);
            doubleReferer(nums);
        }

        private void doubleReferer(int[] nums) {
            int p0 = 0;
            int p1 = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 1) {
                    swap(nums, p1, i);
                    p1 ++;
                } else if (nums[i] == 0) {
                    swap(nums, p0, i);
                    if (p0 < p1) {
                        swap(nums, p1, i);
                    }
                    p0++;
                    p1++;
                }
            }
        }

        private void singleReferer(int[] nums) {
            int ptr = 0;
            for (int i = 0; i < nums.length; i++) {
                 if (nums[i] == 0) {
                     swap(nums, i, ptr);
                     ptr++;
                 }
            }

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 1) {
                    swap(nums, i, ptr);
                    ptr++;
                }
            }
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}